\documentclass[E:/GsjzTle/main/main.tex]{subfiles}
\begin{document}

康托展开可以求解一个排列的排名 , 比如：\(12345\) 排名为 \(1\) ,
\(12354\) 排名为 \(2\)，按字典序增加排名递增，依次类推。

\textbf{拿 \(52413\) 举例子：}

\begin{itemize}
\item
  首先看第一个数
  \(5\)，不管第一位是什么数，后面都有四位数，那么这四位数全排列的方式有
  \(4!\) 种，而如果第一位是 \(1\) 或 \(2\) 或 \(3\) 或 \(4\) 都会比
  \(5\) 开头的字典序要小，所以可以令 \(1\) , \(2\) , \(3\) , \(4\)
  分别作为开头，这样的话就会有 \(4 × 4!\) 种排法要比 \(52413\)
  这种排法的字典序要小。
\item
  那么第一个数是 \(1\) , \(2\) , \(3\) , \(4\)
  时候的字典序的个数数完了是 \(4 × 4!\) 种，且这些字典序都要比 \(52413\)
  的字典序要小。
\item
  还有其他的排列方式比 \(52413\) 的字典序要小的吗？无
\item
  那么就可以固定第一位 \(5\)，找下一位 \(2\) , 这时 \(5\) 已经用过了 ,
  所以从剩下的 \(1，2，3，4\) 里挑选比 \(2\) 小的数，一共 \(1\)
  个，后面还剩三位，也就是 \(3!\) 种排列方式，那么这时候比 \(52413\)
  字典序要小的又有 \(1 × 3!\) 种，也就是当 \(5\) 在第一位，\(1\)
  在第二位的时候。
\item
  再看第三位 \(4\) , 这时 \(5，2\) 都用了，所以从剩下的 \(1，3，4\)
  三个数中找比 \(4\) 小的数的个数，有两个比 \(4\)
  小原理同上，所以这时候也可以有 \(2 * 2!\) 种排列方式的字典序小于
  \(52413\)
\item
  再看第四位 \(1\)，这时候会有 \(0 × 1!\) 种
\item
  再看第五位 \(3\)，这时候会有 \(0 × 0!\) 种
\end{itemize}

\begin{lstlisting}
#include<bits/stdc++.h>
#define rep(i , a , b) for(int i = a ; i <= b ; i ++)
#define int long long
using namespace std;
const int N = 1e6 + 10 , mod = 998244353;
int tree[N << 2] , a[N] , fac[N];
int lowbit(int x)
{
	return x & (-x);
}
void update(int pos , int val)
{
	while(pos <= N - 1)
	{
		tree[pos] += val;
		pos += lowbit(pos);
	}
}
int query(int pos)
{
	int res = 0;
	while(pos)
	{
		res += tree[pos];
		pos -= lowbit(pos);
	}
	return res;
}
void init()
{
	fac[0] = 1;
	rep(i , 1 , N - 10) fac[i] = fac[i - 1] * i % mod;
}
int calc(int n)
{
	int rank = 0;
	rep(i , 1 , n) update(i , 1);
	rep(i , 1 , n)
	{
		rank += fac[n - i] * query(a[i] - 1);
		rank %= mod;
		update(a[i] , -1);
	}
	return rank + 1;
}
signed main()
{
	init();
	int n;
	cin >> n;
	rep(i , 1 , n) cin >> a[i];
	cout << calc(n) << '\n';
	return 0;
}
\end{lstlisting}

\end{document}
